package org.byteDance.l912;

/**
 * @Author yu
 * @Date 2022/3/7
 */
public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        int[] ints = {1, 2, 3, 4};
        System.out.println(solution.sortArray(ints));

    }

    public int[] sortArray(int[] nums) {

        if (nums.length == 0 || nums.length == 1) {
            return nums;
        }

        quickSort(0, nums.length, nums);

        return nums;
    }

    public void quickSort(int left, int right, int[] arr) {
        // 递归终止条件
        if (left >= right) {
            return;
        }

        int l = left;
        int r = right;
        int flag = left;
        int temp = 0;

        while (left < right) {

            // 从右开始遍历
            while (left < right && arr[flag] <= arr[right]) {
                right--;
            }

            if (arr[flag] > arr[right] && flag < right) {
                temp = arr[flag];
                arr[flag] = arr[right];
                arr[right] = temp;
                flag = right;
            }

            // 从左开始遍历
            while (left < right && arr[flag] >= arr[left]) {
                left++;
            }
            if (arr[flag] < arr[left] && flag > left) {
                temp = arr[flag];
                arr[flag] = arr[left];
                arr[left] = temp;
                flag = left;
            }

        }

        quickSort(l, left - 1, arr);
        quickSort(left + 1, r, arr);
    }

}
